\chapter{哈希表}

\section{哈希表}

\subsection{哈希表（Hash Table）}

例如开发一个学生管理系统，需要有通过输入学号快速查出对应学生的姓名的功能。这里不必每次都去查询数据库，而可以在内存中建立一个缓存表，这样做可以提高查询效率。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|}
			\hline
			\textbf{学号} & \textbf{姓名} \\
			\hline
			001121        & Alice         \\
			\hline
			002123        & Bob           \\
			\hline
			002931        & Charlie       \\
			\hline
			003278        & Daniel        \\
			\hline
		\end{tabular}
	}
	\caption{学生名单}
\end{table}

再例如需要统计一本英文书里某些单词出现的频率，就需要遍历整本书的内容，把这些单词出现的次数记录在内存中。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|}
			\hline
			\textbf{单词} & \textbf{出现次数} \\
			\hline
			this          & 108               \\
			\hline
			and           & 56                \\
			\hline
			are           & 79                \\
			\hline
			by            & 46                \\
			\hline
		\end{tabular}
	}
	\caption{词频统计}
\end{table}

因为这些需要，一个重要的数据结构诞生了，这个数据结构就是哈希表。哈希表也称散列表，哈希表提供了键（key）和值（value）的映射关系，只要给出一个key，就可以高效地查找到它所匹配的value。\\

哈希表的时间复杂度几乎是常量$ O(1) $，即查找时间与问题规模无关。\\

哈希表的两项基本工作：

\begin{enumerate}
	\item 计算位置：构造哈希函数确定关键字的存储位置。
	\item 解决冲突：应用某种策略解决多个关键字位置相同的问题。
\end{enumerate}

\vspace{0.5cm}

\subsection{哈希函数（Hash Function）}

哈希的基本思想是将键key通过一个确定的函数，计算出对应的函数值value作为数据对象的存储地址，这个函数就是哈希函数。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw (0,0.5) circle (1) node{h(key)};

		\draw (-4,5) node{key};
		\draw[-] (-5,4) rectangle (-3,3);
		\draw[-] (-5,2) rectangle (-3,1);
		\draw[-] (-5,0) rectangle (-3,-1);
		\draw[-] (-5,-2) rectangle (-3,-3);

		\draw (-4,3.5) node{Alice};
		\draw (-4,1.5) node{Bob};
		\draw (-4,-0.5) node{Charlie};
		\draw (-4,-2.5) node{Daniel};

		\draw (4,5) node{hash table};
		\draw (3,4) rectangle (5,-3);
		\draw (3,3) -- (5,3);
		\draw (3,2) -- (5,2);
		\draw (3,1) -- (5,1);
		\draw (3,0) -- (5,0);
		\draw (3,-1) -- (5,-1);
		\draw (3,-2) -- (5,-2);

		\draw (4,-0.5) node{Alice};
		\draw (4,3.5) node{Bob};
		\draw (4,0.5) node{Charlie};
		\draw (4,-2.5) node{Daniel};

		\draw[dashed, ->] (-3,3.5) -- (-1,0.5);
		\draw[dashed, ->] (-3,1.5) -- (-1,0.5);
		\draw[dashed, ->] (-3,-0.5) -- (-1,0.5);
		\draw[dashed, ->] (-3,-2.5) -- (-1,0.5);

		\draw[dashed, ->] (1,0.5) -- (3,-0.5);
		\draw[dashed, ->] (1,0.5) -- (3,3.5);
		\draw[dashed, ->] (1,0.5) -- (3,0.5);
		\draw[dashed, ->] (1,0.5) -- (3,-2.5);
	\end{tikzpicture}
	\caption{哈希函数}
\end{figure}

哈希表本质上也是一个数组，可是数组只能根据下标来访问，而哈希表的key则是以字符串类型为主的。\\

在不同的语言中，哈希函数的实现方式是不一样的。假设需要存储整型变量，转化为数组的下标就不难实现了。最简单的转化方式就是按照数组长度进行取模运算。\\

一个好的哈希函数应该考虑两个因素：

\begin{enumerate}
	\item 计算简单，以便提高转换速度。
	\item 关键字对应的地址空间分布均匀，以尽量减少冲突。
\end{enumerate}

\vspace{0.5cm}

\subsection{数字关键字的哈希函数构造方法}

对于数字类型的关键字，哈希函数有以下几种常用的构造方法：

\subsubsection{直接定址法}

取关键字的某个线性函数值为散列地址。

\vspace{-0.5cm}

$$
	h(key) = a * key + b
$$

例如根据出生年份计算人口数量h(key) = key - 1990：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|}
			\hline
			\textbf{地址} & \textbf{出生年份} & \textbf{人数} \\
			\hline
			0             & 1990              & 1285万        \\
			\hline
			1             & 1991              & 1281万        \\
			\hline
			2             & 1992              & 1280万        \\
			\hline
			$ \dots $     & $ \dots $         & $ \dots $     \\
			\hline
			10            & 2000              & 1250万        \\
			\hline
			$ \dots $     & $ \dots $         & $ \dots $     \\
			\hline
			21            & 2011              & 1180万        \\
			\hline
		\end{tabular}
	}
	\caption{直接定址法}
\end{table}

\subsubsection{除留余数法}

哈希函数为h(key) = key \% p，p一般取素数。\\

例如h(key) = key \% 17：

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{地址}   & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} \\
			\hline
			\textbf{关键字} & 34         & 18         & 2          & 20         &            &            & 23         & 7          & 42         &            & 27          & 11          &             & 30          &             & 15          &             \\
			\hline
		\end{tabular}
	}
	\caption{除留余数法}
\end{table}

\subsubsection{数字分析法}

分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址。\\

例如取11位手机号码的后4位作为地址h(key) = int(key + 7)。\\

再例如取18位身份证号码中变化较为随机的位数：

\begin{table}[H]
	\centering
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
		\hline
		\textbf{1}               & \textbf{2}               & \textbf{3}               & \textbf{4}               & \textbf{5}               & \textbf{6}               & \textbf{7}               & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} \\
		\hline
		3                        & 3                        & 0                        & 1                        & 0                        & 6                        & 1                        & 9          & 9          & 0           & 1           & 0           & 0           & 8           & 0           & 4           & 1           & 9           \\
		\hline
		\multicolumn{2}{|c|}{省} & \multicolumn{2}{|c|}{市} & \multicolumn{2}{|c|}{区} & \multicolumn{4}{|c|}{年} & \multicolumn{2}{|c|}{月} & \multicolumn{2}{|c|}{日} & \multicolumn{3}{|c|}{辖} & 校验                                                                                                                                                  \\
		\hline
	\end{tabular}
	\caption{数字分析法}
\end{table}

\subsubsection{折叠法}

把关键字分割成位数相同的几个部分，然后叠加。\\

例如将整数56793542每三位进行分割：

\begin{table}[H]
	\centering
	\begin{tabular}{cD{.}{.}{3}}
		  & 542  \\
		  & 793  \\
		+ & 056  \\
		\hline
		= & 1319
	\end{tabular}
\end{table}

\vspace{-1cm}

$$
	h(56793542) = 319
$$

\subsubsection{平方取中法}

计算关键字的平方，取中间几位。\\

例如整数56793542：

\begin{table}[H]
	\centering
	\begin{tabular}{cD{.}{.}{3}}
		  & 56793542         \\
		* & 56793542         \\
		\hline
		= & 3225506412905764
	\end{tabular}
\end{table}

\vspace{-1cm}

$$
	h(56793542) = 641
$$

\vspace{0.5cm}

\subsection{字符串关键字的哈希函数构造方法}

对于字符串类型的关键字，哈希函数有以下几种常用的构造方法：

\subsubsection{ASCII码加和法}

\vspace{-0.5cm}

$$
	h(key) = \left(\sum key[i] \right)\ mod\ N
$$

但是对于某些字符串会导致严重冲突，例如：a3、b2、c1或eat、tea等。\\

\subsubsection{移位法}

取前3个字符移位。

\vspace{-0.5cm}

$$
	h(key) = \left(key[0] \times 27^2 + key[1] \times 27 | key[2] \right)\ mod\ N
$$

对于一些字符串仍然会冲突，例如string、strong、street、structure等。\\

一个有效的改进是涉及关键字中所有n个字符：

$$
	h(key) = \left( \sum_{i=0}^{n-1} key[n-i-1] \times 32^i \right)\ mod\ N
$$

\newpage

\section{哈希冲突}

\subsection{装填因子（Load Factor）}

假设哈希表空间大小为m，填入表中元素个数是n，则称$ \alpha = n / m $为哈希表的装填因子。\\

当哈希表元素太多，即装填因子$ \alpha $太大时，查找效率会下降。实用最大装填因子一般取$ 0.5 \le \alpha \le 0.85 $。当装填因子过大时，解决的方法是加倍扩大哈希表，这个过程叫作再散列（rehashing）。\\

再散列的过程需要遍历原哈希表，把所有的关键字重新散列到新数组中。为什么需要重新散列呢？因为长度扩大以后，散列的规则也随之改变。经过扩容，原本拥挤的哈希表重新变得稀疏，原有的关键字也重新得到了尽可能均匀的分配。\\

装填因子也是影响产生哈希冲突的因素之一。当不同的关键字可能会映射到同一个散列地址上，就导致了哈希冲突（collision），即$ h(key_i) = h(key_j),\ key_i \ne key_j $，因此需要某种冲突解决策略。\\

例如有11个数据对象的集合\{18, 23, 11, 20, 2, 7, 27, 30, 42, 15, 34, 35\}，哈希表的大小为17，哈希函数选择h(key) = key \% size。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{地址}   & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} \\
			\hline
			\textbf{关键字} & 34         & 18         & 2          & 20         &            &            & 23         & 7          & 42         &            & 27          & 11          &             & 30          &             & 15          &             \\
			\hline
		\end{tabular}
	}
\end{table}

在插入最后一个关键字35之前，都没有产生任何冲突。但是h(35) = 1，位置已有对象，就导致了冲突。\\

常用的处理冲突的思路有两种：

\begin{enumerate}
	\item 开放地址法（open addressing）：一旦产生了冲突，就按某种规则去寻找另一空地址。开放地址法主要有线性探测法、平方探测法（二次探测法）和双散列法。

	\item 分离链接法：将相应位置上有冲突的所有关键字存储在同一个单链表中。
\end{enumerate}

\vspace{0.5cm}

\subsection{线性探测法（Linear Probing）}

当产生冲突时，以增量序列1, 2, 3, ..., n - 1循环试探下一个存储地址。\\

例如序列\{47, 7, 29, 11, 9, 84, 54, 20, 30\}，哈希表表长为13，哈希函数h(key) = key \% 11，用线性探测法处理冲突。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{4mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{key}      & \textbf{47} & \textbf{7} & \textbf{29} & \textbf{11} & \textbf{9} & \textbf{84} & \textbf{54} & \textbf{20} & \textbf{30} \\
			\hline
			\textbf{h(key)}   & 3           & 7          & 7           & 0           & 9          & 7           & 10          & 9           & 8           \\
			\hline
			\textbf{冲突次数} & 0           & 0          & 1           & 0           & 0          & 3           & 1           & 3           & 6           \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{2.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{地址}   & \textbf{0}           & \textbf{1}           & \textbf{2} & \textbf{3}           & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7}          & \textbf{8}           & \textbf{9}          & \textbf{10}          & \textbf{11}          & \textbf{12}          & \textbf{$ \Delta $} \\
			\hline
			\textbf{插入47} &                      &                      &            & \textcolor{blue}{47} &            &            &            &                     &                      &                     &                      &                      &                      & 0                   \\
			\hline
			\textbf{插入7}  &                      &                      &            & 47                   &            &            &            & \textcolor{blue}{7} &                      &                     &                      &                      &                      & 0                   \\
			\hline
			\textbf{插入29} &                      &                      &            & 47                   &            &            &            & 7                   & \textcolor{blue}{29} &                     &                      &                      &                      & 1                   \\
			\hline
			\textbf{插入11} & \textcolor{blue}{11} &                      &            & 47                   &            &            &            & 7                   & 29                   &                     &                      &                      &                      & 0                   \\
			\hline
			\textbf{插入9}  & 11                   &                      &            & 47                   &            &            &            & 7                   & 29                   & \textcolor{blue}{9} &                      &                      &                      & 0                   \\
			\hline
			\textbf{插入84} & 11                   &                      &            & 47                   &            &            &            & 7                   & 29                   & 9                   & \textcolor{blue}{84} &                      &                      & 3                   \\
			\hline
			\textbf{插入54} & 11                   &                      &            & 47                   &            &            &            & 7                   & 29                   & 9                   & 84                   & \textcolor{blue}{54} &                      & 1                   \\
			\hline
			\textbf{插入20} & 11                   &                      &            & 47                   &            &            &            & 7                   & 29                   & 9                   & 84                   & 54                   & \textcolor{blue}{20} & 3                   \\
			\hline
			\textbf{插入30} & 11                   & \textcolor{blue}{30} &            & 47                   &            &            &            & 7                   & 29                   & 9                   & 84                   & 54                   & 20                   & 6                   \\
			\hline
		\end{tabular}
	}
	\caption{线性探测法}
\end{table}

线性探测法的缺陷在于容易出现聚集现象。\\

\subsection{平方探测法（Quadratic Probing）}

平方探测法也称为二次探测法，以增量序列$ 1^2, -1^2, 2^2, -2^2, \dots, q^2, -q^2\ (q \le \lfloor N/2 \rfloor) $循环试探下一个存储地址。\\

例如序列\{47, 7, 29, 11, 9, 84, 54, 20, 30\}，哈希表表长为11，哈希函数h(key) = key \% 11，用平方探测法处理冲突。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{4mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{key}      & \textbf{47} & \textbf{7} & \textbf{29} & \textbf{11} & \textbf{9} & \textbf{84} & \textbf{54} & \textbf{20} & \textbf{30} \\
			\hline
			\textbf{h(key)}   & 3           & 7          & 7           & 0           & 9          & 7           & 10          & 9           & 8           \\
			\hline
			\textbf{冲突次数} & 0           & 0          & 1           & 0           & 0          & 2           & 0           & 3           & 3           \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{地址}   & \textbf{0}           & \textbf{1}           & \textbf{2}           & \textbf{3}           & \textbf{4} & \textbf{5} & \textbf{6}           & \textbf{7}          & \textbf{8}           & \textbf{9}          & \textbf{10}          & \textbf{$ \Delta $} \\
			\hline
			\textbf{插入47} &                      &                      &                      & \textcolor{blue}{47} &            &            &                      &                     &                      &                     &                      & 0                   \\
			\hline
			\textbf{插入7}  &                      &                      &                      & 47                   &            &            &                      & \textcolor{blue}{7} &                      &                     &                      & 0                   \\
			\hline
			\textbf{插入29} &                      &                      &                      & 47                   &            &            &                      & 7                   & \textcolor{blue}{29} &                     &                      & 1                   \\
			\hline
			\textbf{插入11} & \textcolor{blue}{11} &                      &                      & 47                   &            &            &                      & 7                   & 29                   &                     &                      & 0                   \\
			\hline
			\textbf{插入9}  & 11                   &                      &                      & 47                   &            &            &                      & 7                   & 29                   & \textcolor{blue}{9} &                      & 0                   \\
			\hline
			\textbf{插入84} & 11                   &                      &                      & 47                   &            &            & \textcolor{blue}{84} & 7                   & 29                   & 9                   &                      & -1                  \\
			\hline
			\textbf{插入54} & 11                   &                      &                      & 47                   &            &            & 84                   & 7                   & 29                   & 9                   & \textcolor{blue}{54} & 0                   \\
			\hline
			\textbf{插入20} & 11                   &                      & \textcolor{blue}{20} & 47                   &            &            & 84                   & 7                   & 29                   & 9                   & 54                   & 4                   \\
			\hline
			\textbf{插入30} & 11                   & \textcolor{blue}{30} & 20                   & 47                   &            &            & 84                   & 7                   & 29                   & 9                   & 54                   & 4                   \\
			\hline
		\end{tabular}
	}
	\caption{平方探测法}
\end{table}

但是只要还有空间，平方探测法就一定能找到空闲位置吗？\\

例如对于以下哈希表，插入关键字11，哈希函数h(key) = key \% 5，用平方探测法处理冲突。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			\textbf{下标} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} \\
			\hline
			\textbf{key}  & 5          & 6          & 7          &            &            \\
			\hline
		\end{tabular}
	}
	\caption{平方探测法存在的问题}
\end{table}

对关键字11进行平方探测的结果一直在下标0和2之间波动，永远无法达到其它空的位置。\\

但是有定理证明，如果哈希表长度是满足$ 4k + 3\ (k \in Z^+) $形式的素数时，平方探测法就可以探查到整个哈希表空间。\\

\subsection{双散列探测法（Double Hashing）}

设定另一个哈希函数$ h_2(key) $，探测序列为$ h_2(key),\ 2h_2(key),\ 3h_2(key), \dots $。\\

探测序列应该保证所有的散列存储单元都应该能够被探测到，选择以下形式有良好的效果：

\vspace{-0.5cm}

$$
	h_2(key) = p - (key\ \%\ p)\ \left(p < N \wedge p, N \in \text{素数}\right)
$$

\vspace{0.5cm}

\subsection{分离链接法}

分离链接法也称拉链法、链地址法，将相应位置上有冲突的所有关键字存储在同一个单链表中。\\

例如关键字序列为\{47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21\}，哈希函数h(key) = key \% 11，用分离链接法处理冲突。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\coordinate (0);
		\foreach \t[count=\i from 0,evaluate=\i as\j using int(\i+1)] in {
				22 $ \rightarrow $ 11,
				89,
				,
				3 $ \rightarrow $ 47,
				37 $ \rightarrow $ 92,
				16,
				94 $ \rightarrow $ 50,
				29 $ \rightarrow $ 7,
				8,
				,
				21
			}
		\node at(\i.south)[anchor=north,draw,minimum height=2em,minimum width=1.5em,outer sep=0pt](\j){}
		node at(\j.west)[align=right,left]{\i}
		node at(\j.east)[align=left,right,xshift=-.7em]{$ \rightarrow $ \t};

		\draw (-3.5,-0.6) rectangle (-2.5,0.6);
		\draw[-] (-3.5,0) -- (-2.5,0);
		\draw (-3,1) node{head};
		\draw (-3,0.3) node{11};
		\draw[->] (-3,-0.3) to[bend left] (0,-0.3);
	\end{tikzpicture}
	\caption{分离链接法}
\end{figure}

\vspace{0.5cm}

\subsection{性能分析}

哈希表的平均查找长度（ASL, Average Search Length）用来度量哈希表查找效率。关键字的比较次数，取决于产生冲突的多少。影响产生冲突多少有三个因素：

\begin{enumerate}
	\item 哈希函数是否均匀
	\item 处理冲突的方法
	\item 哈希表的装填因子$ \alpha $
\end{enumerate}

合理的最大装填因子$ \alpha $应该不超过0.85，选择合适的哈希函数可以使哈希表的查找效率期望是常数$ O(1) $，它几乎与关键字的空间大小n无关。这是以较小的$ \alpha $为前提，因此哈希表是一个以空间换时间的结构。\\

哈希表的存储对关键字是随机的，因此哈希表不便于顺序查找、范围查找、最大值/最小值查找等操作。

\newpage